关于算法：六边形网格，如何找到点在哪个六角形中？ |
您所在的位置：网站首页 › JAVA 存储六边形矩阵 › 关于算法：六边形网格，如何找到点在哪个六角形中？ |
|
我有一张由六边形的行和列组成的地图 我以前使用过正方形网格，由于像素也是正方形，所以比较容易找出选择了哪个正方形， 1234567891011121314 // example where each square is 10 by 10 pixels: private void getClickedSquare(MouseEvent me) { int mouseX = me.getX();// e.g. 25 int mouseY = me.getY();// e.g. 70 int squareX= (int) (mouseX / 10);// in this case 2 int squareY= (int) (mouseY / 10);// in this case 7 //then to access the tile I would do map.squares[squareX][squareY].whatever(); }但是我什至不知道从Hexagons开始，有人有经验吗？ 我无法使用多边形(Java)，因为当我开始在屏幕上移动地图并增加其大小时，每帧更新大量的多边形会遇到问题。虽然这样，我可以检查一下地图瓷砖的任何多边形中是否包含一个点！ 目前显示的六边形只是BufferedImages。 如果您想了解更多信息，请询问， 谢谢您的时间：D 相关讨论 redblobgames.com/grids/hexagons @Pi任何发现此问题的人都应该查看该链接！(已更新：重构代码使内容更易于理解和更有效) (更新：缩短了答案长度，修复了代码中的错误，提高了图像质量)
此图显示了六角形网格的左上角，并且覆盖了一个蓝色方形网格。很容易找到一个点在哪个正方形内，这也可以粗略估计出哪个六角形。六边形的白色部分显示了正方形和六边形网格共享相同坐标的位置，而六边形的灰色部分显示了它们不共享坐标的位置。 现在，解决方案非常简单，只需找到一个点位于哪个方框中，然后检查该点是否在两个三角形中，然后在必要时更正答案即可。 12345678910111213private final Hexagon getSelectedHexagon(int x, int y) { // Find the row and column of the box that the point falls in. int row = (int) (y / gridHeight); int column; boolean rowIsOdd = row % 2 == 1; // Is the row an odd number? if (rowIsOdd)// Yes: Offset x to match the indent of the row column = (int) ((x - halfWidth) / gridWidth); else// No: Calculate normally column = (int) (x / gridWidth);在这一点上，我们有了点所在的框的行和列，接下来，需要针对六边形的两个顶部边缘测试点，以查看我们的点是否位于上方的六边形中的任意一个中： 12345678 // Work out the position of the point relative to the box it is in double relY = y - (row * gridHeight); double relX; if (rowIsOdd) relX = (x - (column * gridWidth)) - halfWidth; else relX = x - (column * gridWidth);具有相对坐标使下一步变得更容易。
就像上图中一样，如果我们的点的y> mx + c，我们知道我们的点位于该线的上方，并且在我们的情况下，该点位于当前行和列的上方和左侧的六边形。请注意，java中的坐标系的y从屏幕左上角的0开始，而不是数学上通常的左下角，因此，左边缘使用负梯度，右边缘使用正梯度。 12345678910111213141516 // Work out if the point is above either of the hexagon's top edges if (relY < (-m * relX) + c) // LEFT edge { row--; if (!rowIsOdd) column--; } else if (relY < (m * relX) - c) // RIGHT edge { row--; if (rowIsOdd) column++; } return hexagons[column][row]; }上例中使用的变量的简要说明：
m是渐变，所以m = c / halfWidth 相关讨论 我什至无法解释这篇文章节省了我多少时间。我对此深表谢意。 没问题:)如果您需要其他任何帮助，请查看我的博客，我的电子邮件已经存在，我的github上有一些开源项目，这些项目只会增加数量:) troygamedev.blogspot.co.uk 旧帖子，显然有用，但是当您引用的网格不是由正方形而是矩形组成时，您总是说"蓝色正方形"。您知道吗？您是说矩形吗？几何图形无法对齐，无法从高边的底部顶点到尖头定向的六边形的顶部绘制正方形。 @pstatix是的，我相信我的意思是矩形。编辑：这个问题比起初我想的要困难，我将通过一些工作重写我的答案，但是我不确定解决方案的路径是否对其他答案有所改善。 这个问题可以改写：给定x，y，找到其中心最接近x，y的六边形 即最小化dist_squared(Hex [n] .center，(x，y))超过n(平方意味着您不必担心平方根会节省一些CPU) 但是，首先我们应该缩小要检查的六边形的数量-我们可以通过以下方法将其缩小到最多5个：
因此，第一步是在UV空间中表达您的点(x，y) 即(x，y)= lambdaU + muV，因此=(lambda，mu)在紫外线空间中 那只是2D矩阵变换(http://playtechs.blogspot.co.uk/2007/04/hex-grids.html如果您不了解线性变换可能会有所帮助)。 现在给定一个点(lambda，mu)，如果我们将它们都舍入到最接近的整数，那么我们得到：
绿色广场内的所有地方都会映射回(2,1) 因此，该"绿色方块"中的大多数点都是正确的，即它们是六边形(2,1)。 但是有些点应该返回六角形＃(2,2)，即：
同样，一些应该返回六角形＃(3,1)。然后在该绿色平行四边形的对角，将还有2个其他区域。 综上所述，如果int(lambda，mu)=(p，q)，则我们可能位于六边形(p，q)内，但也可能位于六边形(p + 1，q)，(p，q + 1)内，(p-1，q)或(p，q-1) 确定几种情况的几种方法。最简单的方法是将所有这五个六角形的中心转换回原始坐标系，并找到最接近我们点的坐标系。 但事实证明，您可以将不进行距离检查的时间缩小到?50％的时间，一次进行距离检查的时间可以缩小到?25％的时间，而进行两次距离检查的其余时间的时间可以缩小到?25％的时间(我猜通过查看每个检查所涉及的区域来确定数字)： 123456p,q = int(lambda,mu) if lambda * mu < 0.0: // opposite signs, so we are guaranteed to be inside hexagon (p,q) // look at the picture to understand why; we will be in the green regions outPQ = p,q1234567else: // circle check distSquared = dist2( Hex2Rect(p,q), Hex2Rect(lambda, mu) ) if distSquared < .5^2: // inside circle, so guaranteed inside hexagon (p,q) outPQ = p,q 12345 else: if lambda > 0.0: candHex = (lambda>mu) ? (p+1,q): (p,q+1) else: candHex = (lambda(u，v，w) 123u = (2/3)*x; v = -(1/3)*x + (1/2)*y; w = -(1/3)*x - (1/2)*y; 然后，就像将u，v和w舍入到最接近的整数然后转换回x，y一样简单。但是有一个主要障碍... 在上面的答案中，请注意，在UV空间中四舍五入将有一些区域无法正确映射：
当使用多维数据集坐标时，仍然会发生这种情况：
橙色三角形中的任何区域距离六边形的中心均大于0.5个单位，并且在四舍五入时会从中心移开。上面显示为红色三角形(在u = 1.5线的左侧)中的任何内容都会使u错误舍入到u = 1而不是u = 2。 不过这里有一些关键的观察... 1.橙色/红色问题区域不重叠 2.在立方体坐标中，有效的十六进制中心的u + v + w =?? 0 在下面的代码中，u，v和w从一开始就被四舍五入，因为如果四舍五入的坐标不为零，则仅在四舍五入的情况下才进行四舍五入。 123uR = Math.round(u); vR = Math.round(v); wR = Math.round(w);如果这些总和不为零，因为问题区域不重叠，那么将只有1个错误地四舍五入的坐标。该坐标也是最圆的坐标。 12arr = [ Math.abs(u-uR), Math.abs(v-vR), Math.abs(w-wR) ]; var i = arr.indexOf(Math.max(...arr));找到问题坐标后，将在另一个方向上四舍五入。然后根据四舍五入/校正后的(u，v，w)计算最终值(x，y)。 1234567891011121314151617181920212223242526272829303132333435nearestHex = function(x,y){ u = (2/3)*x; v = -(1/3)*x + (1/2)*y; w = -(1/3)*x - (1/2)*y; uR = Math.round(u); vR = Math.round(v); wR = Math.round(w); if(uR+vR+wR !== 0){ arr = [ Math.abs(u-uR), Math.abs(v-vR), Math.abs(w-wR) ]; var i = arr.indexOf(Math.max(...arr)); switch(i){ case 0: Math.round(u)===Math.floor(u) ? u = Math.ceil(u) : u = Math.floor(u); v = vR; w = wR; break; case 1: Math.round(v)===Math.floor(v) ? v = Math.ceil(v) : v = Math.floor(v); u = uR; w = wR; break; case 2: Math.round(w)===Math.floor(w) ? w = Math.ceil(w) : w = Math.floor(w); u = uR; v = vR; break; } } return {x: (3/2)*u, y: v-w}; }这是SebastianTroy的答复的附录。我将其留为评论，但我的声誉还不够。 如果要实现如下所述的轴向坐标系： http://www.redblobgames.com/grids/hexagons/ 您可以对代码进行一些修改。 代替 12345// Is the row an odd number? if (rowIsOdd)// Yes: Offset x to match the indent of the row column = (int) ((x - halfWidth) / gridWidth); else// No: Calculate normally column = (int) (x / gridWidth);用这个 12float columnOffset = row * halfWidth; column = (int)(x + columnOffset)/gridWidth; //switch + to - to align the grid the other way这将使坐标(0，2)与(0，0)和(0，1)在同一对角线上，而不是在(0，0)的正下方。 相关讨论 不错，我没有考虑过轴向坐标系，可以修改我的答案以包括您的观点，但我不想剥夺您的声誉！ 对于任何学习如何实现十六进制网格的人来说，该链接都是一个绝佳的资源。 :-)我不知道这是否会帮助任何人，但我想出了一个简单得多的解决方案。当我创建自己的Hexagon im时，只需给它们一个中间点，然后通过用鼠标协调找到最接近的中间点，就可以找到一个im！ 相关讨论 也许您可以提供一个例子。 您如何知道要测试鼠标指向的四个最接近的六角形？我再看了一下http://playtechs.blogspot.co.uk/2007/04/hex-grids.html，从数学上讲它非常整洁。 然而，塞巴斯蒂安的方法似乎确实切合实际，并以很少的几行代码完成了任务。 如果您阅读了注释部分，则会发现有人在http://gist.github.com/583180上编写了Python实现。 为了后代，我在此重申： 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364# copyright 2010 Eric Gradman # free to use for any purpose, with or without attribution # from an algorithm by James McNeill at # http://playtechs.blogspot.com/2007/04/hex-grids.html # the center of hex (0,0) is located at cartesian coordinates (0,0) import numpy as np # R ~ center of hex to edge # S ~ edge length, also center to vertex # T ~"height of triangle" real_R = 75. # in my application, a hex is 2*75 pixels wide R = 2. S = 2.*R/np.sqrt(3.) T = S/2. SCALE = real_R/R # XM*X = I # XM = Xinv X = np.array([ [ 0, R], [-S, S/2.] ]) XM = np.array([ [1./(2.*R), -1./S], [1./R, 0. ] ]) # YM*Y = I # YM = Yinv Y = np.array([ [R, -R], [S/2., S/2.] ]) YM = np.array([ [ 1./(2.*R), 1./S], [-1./(2.*R), 1./S], ]) def cartesian2hex(cp): """convert cartesian point cp to hex coord hp""" cp = np.multiply(cp, 1./SCALE) Mi = np.floor(np.dot(XM, cp)) xi, yi = Mi i = np.floor((xi+yi+2.)/3.) Mj = np.floor(np.dot(YM, cp)) xj, yj = Mj j = np.floor((xj+yj+2.)/3.) hp = i,j return hp def hex2cartesian(hp): """convert hex center coordinate hp to cartesian centerpoint cp""" i,j = hp cp = np.array([ i*(2*R) + j*R, j*(S+T) ]) cp = np.multiply(cp, SCALE) return cp我知道这已经很晚了，但是我目前正在使用六角形网格，并试图找到解决该问题的方法。繁重的数学方法对我来说似乎有些矫kill过正，但是我知道它们为什么起作用以及如何起作用。几乎偶然地，我找到了一个超级简单的解决方案，可以用几行代码完成。 在我的示例中，我有一个自定义的Hexagon类，其中包含一个成员Point变量，该成员变量存储六边形中心的(x，y)。然后，我根据该中心值计算并绘制六边形。 每个Hexagon类还附加到Tile行，后者存储一行和col变量(绘制网格时给出)。 所需变量： -半径 -网格行 -网格列 -六角中心点 -鼠标点击点(或其他给定点) -瓷砖/六边形的清单 我的mouseListener： 12345678910111213141516171819202122addMouseListener(new MouseAdapter() { @Override public void mouseClicked(MouseEvent e) { super.mouseClicked(e); System.out.println("Mouse Click Registered"); double closestDistance = Double.MAX_VALUE; int closestIndex = -1; for (int i = 0; i < tiles.size(); i++) { double distance = tiles.get(i).getDistance(new myPoint(e.getX(), e.getY())); if (distance < closestDistance) { closestDistance = distance; if (closestDistance -1) { Tile t = tiles.get(closestIndex); System.out.println("Selected tile:" + t.getCol() +"," + t.getRow()); } } });我的计算是从Tile类执行的： 123456public double getDistance(myPoint p) { myPoint center = this.hexagon.getCenter(); double xd = center.x - p.x; double yd = center.y - p.y; return Math.abs(Math.sqrt((xd * xd) + (yd * yd))); }这是做什么的。浏览地图上的六边形列表，计算从指定点到六边形中心点的距离的绝对值。如果该距离小于先前计算的距离，则将该值设置为最小值。如果该数字小于半径，则将最近索引设置为该索引号。继续直到磁贴循环结束。 循环后，验证值索引已保存，如果已保存，则选择该索引。 注意：可以通过从指定点计算行/列来进一步优化。有了这些信息，您就可以将正在遍历的图块的数量限制为听起来像该点的图块。 相关讨论 感谢您抽出宝贵的时间来回答问题，如果您查看我的答案，就会发现它只是"查找行和列，然后再做几次额外的检查"，而不是"高数学"！您的方法处理起来非常繁琐，并且适合少量的十六进制和不经常检查的对象，但是如果使用成千上万的十六进制并且每次鼠标移动检查，这将是一个麻烦的问题。我发现了另一种查看鼠标是否在六边形中的方法。使用一点点的trigger，您可以找到鼠标与六边形中心之间的直线的角度，使用该角度，您可以计算出从六边形的中心到六边形的边缘的直线的长度角度。然后，只需检查鼠标之间的线的长度小于六边形边缘的预期长度即可。如果有人想要示例代码，我可以分享。 相关讨论 那么，如何选择六边形来进行初始trig计算呢？还是您遍历每个六角形并检查直到找到合适的六角形？在检查线长时，您是否也将六角形近似为一个圆？如果不是，那么我将对在给定角度下计算六角形"半径"的代码超级感兴趣！ |
| CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |